
// merge_sort.h
#ifndef __MERGE_SORT_H__
#define __MERGE_SORT_H__

#include <cstdio>
#include <functional>

template<typename T, typename C>
void merge(T* a, int begin, int mid, int end, T* temp, C cmp)
{
    int first_part_pos = begin;
    int first_part_end = mid;
    int second_part_pos = mid + 1;
    int second_part_end = end;
    int temp_pos = 0;
    while (first_part_pos <= first_part_end && second_part_pos <= second_part_end)
    {
        if(cmp(a[first_part_pos],a[second_part_pos]))
        {
            temp[temp_pos++] = a[first_part_pos++];
        }
        else
        {
            temp[temp_pos++] = a[second_part_pos++];
        }
    }
    while (first_part_pos <= first_part_end)
    {
        temp[temp_pos++] = a[first_part_pos++];
    }
    while (second_part_pos <= second_part_end)
    {
        temp[temp_pos++] = a[second_part_pos++];
    }
    for (int i = 0; i < temp_pos; i++)
    {
        a[begin + i] = temp[i];
    }
}

template<typename T, typename C>
void merge_logic(T* a, int begin, int end, T* temp, C cmp)
{
    if(begin < end)
    {
        int mid = (begin + end) / 2;
        merge_logic(a, begin, mid, temp, cmp);
        merge_logic(a, mid+1, end, temp,cmp);
        merge(a, begin, mid, end, temp, cmp);
    }
}

template<typename T, typename C>
void merge_sort(T* a, int n, C cmp)
{
    T* temp = new T[n];
    merge_logic(a, 0, n-1, temp,cmp);
    delete []temp;
}
/*
int main()
{
    int a[] = {20,3,15,32,49,8,4,64,3,13,6,1,6,6,4456,4};
    printf("before sort:\n");
    for(int i=0; i<sizeof(a)/sizeof(int); ++i)
    {
        printf("%d ",a[i]);
    }
    printf("\n");
    merge_sort(a, sizeof(a)/sizeof(int), std::greater_equal<int>());
    printf("after sort:\n");
    for(int i=0; i<sizeof(a)/sizeof(int); ++i)
    {
        printf("%d ",a[i]);
    }
    printf("\n");
    return 0;
}
*/

#endif //__MERGE_SORT_H__